Date: Wed, 20 Nov 1996 22:32:35 GMT
Server: Apache/1.0.3
Content-type: text/html
Content-length: 15327
Last-modified: Fri, 03 May 1996 19:28:53 GMT

<TITLE>C251 Course Description</TITLE>

<H2>S251 -- Foundations of Digital Computing (3 cr)</H2>

<IMAGE ALIGN=top SRC="img/new_tiny.gif">

<UL>
<LI> <!WA0><a href="http://www.cs.indiana.edu/classes/s251/grades/grades.txt"> <b> Grades </b> </a> have been posted.
<LI> <!WA1><a href="http://www.cs.indiana.edu/classes/s251/exam/e2a.txt"> Solutions </a>
     to the questions on the final examination have been posted.
</UL>

<H3>Contents</H3>
<UL>
<LI> <!WA2><A HREF="http://www.cs.indiana.edu/classes/s251/img/students.html"><B> Directory </B> of current S251 students</A>
<LI> <!WA3><A HREF="#general">General information</A>
<LI> <!WA4><A HREF="#textbook">Textbook</A>
<LI> <!WA5><A HREF="#description">Course description</A>
<LI> <!WA6><A HREF="#syllabus">Syllabus and supplementary material</A>
     <UL>
     <LI> <!WA7><A Href="#problemassignments"> Problem presentations
     <LI> <!WA8><A Href="#homework"> Homework
     </UL>
<LI> <!WA9><A HREF="#grading">Grading and gradebooks</A>
<LI> <!WA10><A HREF="#communication">Communication</A>
<LI> <!WA11><A HREF="#evaluation">Course evaluations</A>
<LI> <!WA12><A HREF="#policies">Policies</A>
</UL>
<A NAME="general"><H3>General Information</H3></A>

This is CSCI S251, Section 2126, Second Semester 1995-96.

<H3> Instructors </H3>

<table>
<td rowspan=3>
 <!WA13><A HREF="http://www.cs.indiana.edu/usr/local/www/foto/sjohnson.gif">
 <IMAGE
  ALIGN=top
  SRC="http://www.cs.indiana.edu/picons/db/users/edu/indiana/sjohnson/face.gif"
  photo</image></A>
<td>
 <!WA14><A HREF="http://www.cs.indiana.edu/hyplan/sjohnson.html">
 <B> Steven D. Johnson</B></A>, Associate Professor 
<tr>
<td>
 <!WA15><A HREF="mailto:sjohnson@cs.indiana.edu"><EM>
    sjohnson@cs.indiana.edu</EM></A>
<tr>
<td> Office hours:
     Tue. and Thu. 2:30-3:30pm in Lindley 330F, or by arrangement
<tr>
<td rowspan=3>
 <IMAGE ALIGN=top SRC="img/Newkirk.little.gif" </image>
<td>
 <!WA16><A HREF="http://www.cs.indiana.edu/hyplan/jnewkir.html">
 <B>Jim Newkirk</B></A>, Associate Instructor
<tr>
<td> <!WA17><A HREF="mailto:jnewkir@cs.indiana.edu"><EM>jnewkir@cs.indiana.edu</EM></A>
<tr>
<td> Office hours:
     Wed. 1:00-3:00pm (tentative) in Lindley 330I, or by arrangement
</table>

<H3> Meetings </H3>

<DL PACKED>
<DT> Lectures: TR 1:00-2:15pm in Balentine Hall, Room 335 (BH335).
<DT> Demonstrations: Lindley Hall, Room 115 (LH115) during lecture periods,
     as announced.
<DT> Discussion: W 7:15-9:15pm in Lindley Hall, Room 102 (LH102).
     <em> No regular meetings. </em>
     This time is scheduled for reviews, examinations, and possible
     discussions.
</DL>

<H3>Prerequisites</H3>
C211, M215, and as a prerequisite or corequisite C212.
This is the "honors" version of C251 and participants must be enrolled as
Honors Division  students.  It is assumed that you have taken C211 here
at Indiana, and so are familiar with the Scheme programming language.
The particular skills needed are the ability to program in a symbolic
programming language and the experience of programming with recursion.

<A NAME="textbook"><H3>Textbook</H3></A>

We will use the textbook <I>Logic and Discrete Mathematics</I> by
Winfried Karl Grassmann and Jean-Paul Tremblay (Prentice-Hall, 1996).
At this time the text book is on order; it has not arrived at the book stores
yet.

<A NAME="description"><H3>Course Description</H3></A>

The mathematical foundations of computer science differ somewhat from
from those of the physical and social sciences.  The study of computation
has two main branches, performance and meaning.  In formalizing
performance we focus on combinatorics and statistics, whose foundations
are included in "traditional" mathemematics.  In formalizing meaning
we draw more heavily on logic, both as a way to express ideas about programs
and as a discipline for describing what computers are and what they do.

<P>
Computation takes place in a discrete <em> digital </em> domain where all
phenomena ultimately reduce to binary <b>1</b>s and <b>0</b>s.
To explore this universe we need different mathematical tools than are
used by physicists and chemists.  We use <em> induction </em> far more
often than differentiation or integration, for example, and will see
numerous styles of inductive reasoning in this course.  We will also
explore discrete mathematical structures, trees and other graphs, that
are prevalent in computing.

<P>
The main goal of the course is to improve each participant's ability
to conduct a rigorous mathematical argument, that is, to do proofs.
One reason (not the only one) we look at logic in this course is for the
purpose of evaluating proof narratives.  A central idea of this course
is that "doing a proof" and "programming" are pretty much the same activities.
The better you are at proving, the better programmer you will be.
More important, the better computer scientist you will become.

<P>
I plan to follow the text book, except for Chapters 4 (Prolog),
8 (Specification in Z), and 12 (Relational Database Systems).  I may
have to skip more chapters, depending on our progress through the material.
I may also introduce some topics from later chapters as we go along.
There are a few topics not in the text that we may look at, again, if there
is time.  In any event, I will cover all the material of a core 251 course.

<A NAME="syllabus"><H3>Syllabus and supplementary material </H3></A>

One or two weeks will be devoted to each of the chapters listed below.
Supplementary material is (or will be) included below the chapter listing in
some cases. This is an <EM>evolving syallabus</EM>, which will grow as
the course develops.  Check it weekly for new additions to the supplementary
material.

<UL>
<LI> Chapter 1: Propositional Logic (2 weeks)
 <UL>
 <LI> <!WA18><A HREF="http://www.cs.indiana.edu/classes/s251/hw/probs.ch1.txt"><B>problem assignments</B></A>
 <LI> <!WA19><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/tt.ss">pgm/tt.ss</A>, a truth table generator in Scheme.
 <LI> <!WA20><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/sets.ss">pgm/sets.ss</A>, set operations in Scheme.
 <LI> <!WA21><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/dnf.ss">pgm/dnf.ss</A>, a DNF generator
 <LI> Notes from meetings:
      <UL>
      <LI> <!WA22><A HREF="http://www.cs.indiana.edu/classes/s251/lec/1">1st</A> January 9
      <LI> <!WA23><A HREF="http://www.cs.indiana.edu/classes/s251/lec/2">2nd</A> January 11
      <LI> <!WA24><A HREF="http://www.cs.indiana.edu/classes/s251/lec/3">3rd</A> January 16
      <LI> <!WA25><A HREF="http://www.cs.indiana.edu/classes/s251/lec/4">4th</A> January 18
      <LI> <!WA26><A HREF="http://www.cs.indiana.edu/classes/s251/lec/5">5th</A> January 23
      <LI> <!WA27><A HREF="http://www.cs.indiana.edu/classes/s251/lec/6">6th</A> January 25
      </UL>
 <LI> <!WA28><A HREF="http://www.cs.indiana.edu/classes/s251/suppl/parse-1.ps"> Parsing Example (ps)</a>:
 <LI> <!WA29><A href="http://www.cs.indiana.edu/classes/s251/suppl/PFdiagrams.ps"> Proof Diagrams (ps)</A>
 </UL>
<LI> Chapter 2 (and maybe 11): Predicate Calculus (2 weeks)
 <UL>
 <LI> <A NAME="problemassignments">
      <!WA30><A HREF="http://www.cs.indiana.edu/classes/s251/hw/probs.ch2.txt"><B>problem assignments</B></A></A>
 <LI> Notes from meetings:
      <UL>
      <LI> <!WA31><A HREF="http://www.cs.indiana.edu/classes/s251/lec/7">7th</A> January 30
      <LI> <!WA32><A HREF="http://www.cs.indiana.edu/classes/s251/lec/8">8th</A> February 1
      <LI> <!WA33><A HREF="http://www.cs.indiana.edu/classes/s251/lec/9-10">9th and 10th</A> February 6 and 8
      <LI> <!WA34><A HREF="http://www.cs.indiana.edu/classes/s251/lec/11">11th</A> February 12
      <LI> <!WA35><A HREF="http://www.cs.indiana.edu/classes/s251/lec/12">12th</A> February 14
      </UL>
 <LI> <!WA36><A HREF="http://www.cs.indiana.edu/classes/s251/pgm/u.ss">pgm/u.ss</A>, a <em>unification</em> algorithm.
 <LI> <!WA37><a href="http://www.cs.indiana.edu/classes/s251/exam/e1-handout.ps"> Summary sheet </a>, laws of boolean
      algebra, propositional logic, equational logic, and predicate logic.
 </UL>
<LI> Chapter 3:  Induction and Recursion (4 weeks)
  <UL>
  <LI> Skim Sections 3.2 and 3.5
  <LI> Notes from meetings:
      <UL>
      <LI> <!WA38><A HREF="http://www.cs.indiana.edu/classes/s251/lec/13-15"> 13, 14, 15 </a> February 20 through March 5
      </UL>
  </UL>
<LI> Chapter 9: Program Correctness Proofs (1-2 weeks)
  <UL>
  <LI> Notes from meetings:
      <UL>
      <LI> <!WA39><A HREF="http://www.cs.indiana.edu/classes/s251/lec/inprogress">16th-?</A> partial notes for lectures
           on while programs, their meanings, and Hoare logic.
      </UL>
  <LI> The <!WA40><A href="http://www.cs.indiana.edu/classes/s251/suppl/Hoare.ps"> Hoare Calculus </a> for program
       proofs--summary of the inference rules.
  </UL>
<LI> Chapter 6.3-6.5: More on Functions (1 week)
   <UL>
     <LI> <!WA41><a href="http://www.cs.indiana.edu/classes/s251/suppl/split.txt">Code of the <em> split </em> function </a>.
   </UL>
<LI> <em> tentative</em> Chapter 7: Graphs and Trees (1 week)
<LI> <em> tentative</em> Chapter 10: Grammars, Languages, and Parsing
       (1-2 weeks)
<LI> <em> tentative </em> Selected topics: time permitting
</UL>

<A NAME="assignments"><H3>Homework assignments</H3></A>

In studying the textbook material, you should work enough exercises and
problems in the text to ensure that you understand the material.
Since many of the discussions in class will derive from these exercises,
we should be certain that at least one individual has worked through every
one of them, so every problem has assigned to it one or two students who
are expected to be able to present the problem at a class meeting.
These assignments are maintained in the <A syllabus.

Any homework assignments and "challenges" will be posted here and on the
<A NAME="communication">s251 newsgroup</a>.  Most homeworks will not be graded
for credit; the purpose of these assignments is to guide participants
in preparing for the presentation of material in the class, and to show
the kinds of problems that will be asked on examinations.
<em> Challenges </em> are homework assignments that are offered for
credit.  These will be clearly indicated when posted.

<A NAME="homework">
<UL>
<LI> <!WA42><A href="http://www.cs.indiana.edu/classes/s251/hw/1.txt">Homework Assignment One</A>
<LI> <!WA43><A href="http://www.cs.indiana.edu/classes/s251/hw/2.txt">Homework Assignment Two</A>
     <em><b>Due Monday, February 5, in class.</b></em>
<LI> <!WA44><A href="http://www.cs.indiana.edu/classes/s251/hw/3.html">Homework Assignment Three</A>
     <em><b>Due Thursday, February 29, in class.</b></em>
<LI> <!WA45><A href="http://www.cs.indiana.edu/classes/s251/hw/4.txt">Homework Assignment Four</A>.  
     <!WA46><A href="http://www.cs.indiana.edu/classes/s251/hw/4a.txt"><B>Solutions</B> </a> are posted.
<LI> <!WA47><A href="http://www.cs.indiana.edu/classes/s251/hw/5.txt">Homework Assignment Five</a>
     (given in class on April 2)
     <em><b>Due Thursday, April 4, in class.</b></em>
<LI> <!WA48><A href="http://www.cs.indiana.edu/classes/s251/hw/6.txt">Homework Assignment Six</A>
     <em><b>Due Thursday, April 18, in class.</b></em>
     <!WA49><A href="http://www.cs.indiana.edu/classes/s251/hw/6a.txt"><B>Solutions</B> </a> are posted.
</UL>

<P>
In this course, you are welcome to discuss assignments, presentations,
and challenges with other students.
<EM>Do not assume this is true in all your courses!</EM>
Teamwork in doing assignments is good as long as each
member of the team contributes, and fully understands the assignment.
If you are working with a group, please indicate it on your homework
papers.  If someone has given you a lot of help, acknowledge them;
you will not be penalized and they will get the thanks they deserve.
<P>

<A NAME="grading"><H3>Grading and gradebooks</H3></A>

The gradebook will be posted on this home page and updated regularly.
<ul><ul>
<li> <!WA50><a href=http://www.cs.indiana.edu/classes/s251/grades/mar28.text>Thu Mar 28 11:16:24 EST 1996</a>
<li> <!WA51><a href=http://www.cs.indiana.edu/classes/s251/grades/apr03.txt>Wed Apr  3 16:34:46 EST 1996</a>
<li> <!WA52><a href=http://www.cs.indiana.edu/classes/s251/grades/grades.txt>Fri May  3 13:02:36 EST 1996</a>
</ul></ul>

The listing of evaluation criteria shown below is tentative.  For this
honors class I would like to place greater emphasis on interation and
participation than on formal examinations and assignments.  However,
the form of participation is something I would like to discuss at the
first meeting of the class.  Also, since I am required to enter a grade
for each participant at the end of the semester, some objective performance
comparison will be necessary.

<UL PLAIN>
<LI><STRONG> 35% for paricipation,</STRONG> including classroom presentations,
    class discussion, posted challenges, and projects.
<LI><STRONG> 20% for Exam 1, </STRONG>
   to be scheduled during the discussion session (W, 7:15-9:15),
   week and location to be announced.
<LI><STRONG> 20% for Exam 2, </STRONG>
   to be scheduled during the discussion session (W, 7:15-9:15),
   week and location to be announced.
<LI><STRONG> 25% for the Final Exam. </STRONG>
   Currently scheduled for Tuesday, April 30, 12:30-2:30pm;
   location to be announced. 
</DL>


<A NAME="communication"><H3>Communication</H3></A>

This <!WA53><A href=http://www.cs.indiana.edu/classes/s251/home.html> home page </A>
is the primary distribution point for information as the course progresses.
Please check it regularly.

<P>
The course newsgroup,
<!WA54><A NAME=1 HREF="news:ac.csci.s251">ac.csci.c251</A>
used to post announcements, such as assignments, exams, and any exceptions
to our usual office hours.  You are also encouraged to use it to post
questions related to the course, participate in discussions, or share related
information with the class.  Please make a habit of looking for new notes
a few times each week.

<P>
On individual matters, please feel free to contact your instructor or
associate instructor via email or to drop by their office.  The
scheduled office hours are reserved for S251 students, but you are welcome
and encouraged to drop by at other times.

<A NAME="evaluation"><H3>Course Evaluation</H3></A>

Participants are strongly encouraged to use the department's
World-Wide-Web based course evaluation system, which can be accessed
through the Computer Science Department's
 <!WA55><A HREF="http://www.cs.indiana.edu">home page</A>.
Evaluation summaries will be extracted two times during the semester.
During the first three weeks, students will be asked to provide feedback
on all aspects of the course, providing an early opportunity to inform
the instructors about how the course should be run.

<P>
Final course evaluations are taken seriously by the department and are
integral to yearly faculty and department evaluations.
To encourage participation, credit 
will be given to those students who submit a full evaluation during the
week prior to final examinations.  The evaluations are <EM>anonymous</EM>,
but a transaction record is generated whenever an individual evaluation
is updated. These transaction records are compiled and sorted by the
Undergraduate Secretary.  Thus, the instructor is informed about <EM>who</EM>
filed evaluations independently of what those evaluations may contain.
Final evaluation <EM>content</EM> will not be reviewed by the instructor until
after grades are assigned.

<A NAME="policies"><H3>Policies</H3></A>

<B> Attendence</b>.
Not all the material presented in this course is in the text book.
Class attendance is not monitored and is not mandatory, although
regular attendance and class participation are a factor in
<!WA56><A HREF="#participation">grading</A>.   Attendance at examinations
is mandatory and make-up examinations will normally not be given.
No special assignments or projects will be given to help students
raise their grades.  

<P>
<B> Academic Integrity</b>.
If you have not already done so, please read the Computer Science Department's
<!WA57><A HREF="http://www.cs.indiana.edu/integrity.html"><EM>Statement on Academic
Integrity</EM></A> to be sure you understand the rules under which computer
science courses operate.  Cases of academic dishonesty will be reported
to the Office of Student Ethics, a branch of the Office of the Dean of
Students.

<P>
<B>Withdrawal</B>.
Wednesday, March 6, is the last day to drop a course or
withdraw from all courses with an automatic W.  After that date, a
student may withdraw only with the permission of his or her dean.
This approval is normally only for urgent reasons related to
extended illness or equivalent distress.   <P>

<P>
<B>Incompletes</B>.
An incomplete (I) final grade will be given only
in exceptional circumstances conforming to university and departmental
policies which requires, among other things, that the student must have
completed the bulk of the work required for the course with a passing
grade, and that the remaining work can be made up within 30 days after
the end of the semester. If these conditions cannot be met withdrawal
is the appropriate course of action. <P>
